#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
using namespace std;
using ll = int64_t;

__attribute__((always_inline)) static vector<ll> sub(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return {0};
    }
    int tot = 1 << n;
    vector<ll> res(tot, 0);
    for (int i = 0; i < tot; i++) {
        ll sum = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                sum += nums[j];
            }
        }
        res[i] = sum;
    }
    return res;
}

int main() {
    iostream::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    int n, q;
    scanf("%d %d", &n, &q);
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }

    int n1 = n / 2;
    int n2 = n - n1;
    vector<int> A, B;
    for (int i = 0; i < n1; i++) 
        A.push_back(v[i]);
    for (int i = n1; i < n; i++)
        B.push_back(v[i]);

    vector<ll> sumA = sub(A);
    vector<ll> sumB = sub(B);

    sort(sumA.begin(), sumA.end());
    sort(sumB.begin(), sumB.end());

    int lenA = sumA.size();
    int lenB = sumB.size();
    ll maxB = lenB > 0 ? sumB[lenB - 1] : 0;

    while (q--) {
        ll l, r;
        scanf("%lld %lld", &l, &r);
        ll ans = 0;
        int p = 0, q_idx = 0;
        for (int i = lenA - 1; i >= 0; i--) {
            ll a = sumA[i];
            if (a < l - maxB) {
                break;
            }
            ll L = l - a;
            ll R = r - a;

            while (p < lenB && sumB[p] < L)
                p++;
            while (q_idx < lenB && sumB[q_idx] <= R)
                q_idx++;
            ans += (q_idx - p);
        }
        printf("%lld\n", ans);
    }
    return 0;
}